# -*- coding:utf-8 -*-
List = list
# 给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
# 示例 1：
# 输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
# 输出：6
# 解释：最大矩形如上图所示。

# 示例 2：
# 输入：matrix = [["0"]]
# 输出：0

# 示例 3：
# 输入：matrix = [["1"]]
# 输出：1

# rows == matrix.length
# cols == matrix[0].length
# 1 <= row, cols <= 200
# matrix[i][j] 为 '0' 或 '1'

# 思路错误：
# 思考过程
# 1、生成matrix上[row, col]对应的格子，组成的[width, height]
# eg:
# [1, 0, 1, 0, 0]
# [1, 0, 1, 1, 1]
# [1, 1, 1, 1, 1]
# [1, 0, 0, 0, 0]
# 对应生成的数据
# [(1,1), (0,0), (1,1), (0,0), (0,0)]
# [(1,2), (0,0), (1,2), (0,0), (0,0)]
# [(1,3), (2,1), (?,?), (0,0), (0,0)]
# [(1,4), (0,0), (0,0), (0,0), (0,0)]
# 可以观察到(?,?)的位置既可以是(1,3)也可以是(3,1)
# 2、先生成(1,3)计算出最大值，在生成(3,1)计算出最大值
# 
# 出现的问题：
# [0, 0, 0, 1, 0]
# [0, 0, 0, 1, 0]
# [0, 0, 1, 1, 0]
# [1, 1, 1, ?, 0]
# 可以看到?这个位置的数据可以是(1,4),(4,1),(2,2)打乱了上面的思路

# class Solution:
#     def maximalRectangle(self, matrix: List[List[str]]) -> int:
#         map = [[[0,0] for i in range(len(matrix[0]) + 1)] for j in range(len(matrix) + 1)]
#         for r in range(len(matrix)):
#             for c in range(len(matrix[0])):
#                 if matrix[r][c] == "0":
#                     continue
#                 row = r + 1
#                 col = c + 1
#                 cur = map[row][col]
#                 up = map[row - 1][col]
#                 lf = map[row][col - 1]
#                 cur[0] = min(max(up[0], 1), lf[0] + 1)
#                 cur[1] = up[1] + 1
                
#         max = 0
#         for r in range(len(matrix)):
#             for c in range(len(matrix[0])):
#                 n = map[r + 1][c + 1]
#                 if n[0] * n[1] > max:
#                     max = n[0] * n[1]                      
#         return max

# 查看官方解决方案，把矩形转换成一系列柱状图进行解决问题
class Solution:
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        map = [[0 for i in range(len(matrix[0]) + 1)] for j in range(len(matrix) + 1)]
        for r in range(len(matrix)):
            for c in range(len(matrix[0])):
                if matrix[r][c] == "0":
                    continue
                map[r + 1][c + 1] = map[r][c + 1] + 1
        max = 0
        for r in range(len(matrix), -1, -1):
            stack = [-1]
            column = map[r]
            for i in range(len(column)):
                while len(stack) > 1 and column[i] < column[stack[-1]]:
                    area = (i - stack[-2] - 1) * column[stack[-1]]
                    if area > max:
                        max = area
                    stack.pop()
                stack.append(i)
            while len(stack) > 1:
                area = column[stack[-1]] * (len(column) - stack[-2] - 1)
                if area > max:
                    max = area
                stack.pop()
            if max >= r * len(matrix[0]):
                return max
                        
                
        
    
t = Solution()
print(t.maximalRectangle([["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]))